package com.ds.tree;

public class AvlTree<T extends Comparable<? super T>> {

	private AvlNode<T> root;
	
	public void insert(T t){
		
		root = insert(t,root);
		
		
	}
	
	public AvlNode<T> insert(T t,AvlNode<T> node){
		
		if(node == null) {
			return new AvlNode<T>(t);
		}
		
		if(t.compareTo(node.t) > 0) {
			node.right = insert(t,node.right);
			
			if(height(node.right) - height(node.left) == 2) {
				
				if(t.compareTo(node.right.t) > 0) {
					node = repWithRight(node);
				}else {
					node = repDoubleRight(node);
				}
			}
			
		}else if(t.compareTo(node.t) < 0) {
			node.left = insert(t,node.left);
			
			if(height(node.left) - height(node.right) == 2) {
				
				if(t.compareTo(node.left.t) > 0) {
					node = repDoubleLeft(node);
				}else {
					node = repWithLeft(node);
				}
			}
			
		}
		node.height = Math.max(height(node.left),height(node.right)) + 1 ;
		return node;
	}
	
	public void remove(T t) {
		
		root = remove(t,root);
		
	}
	
	private AvlNode<T> remove(T t,AvlNode<T> node){
		
		if(t == null) {
			return null;
		}
		
		int result = t.compareTo(node.t);
		
		if(result < 0) {
			node.left = remove(t,node.left);
			
			if((height(node.right) - height(node.left)) == 2) {
				
				if(height(node.right.left) > height(node.right.right)) {
					node = repDoubleRight(node);
				}else {
					node = repWithRight(node);
				}
				
			}
			
		}else if(result > 0) {
			node.right = remove(t,node.right);
			
			if((height(node.left) - height(node.right)) == 2) {
				if(height(node.left.right) > height(node.left.left)) {
					node = repDoubleLeft(node);
				}else {
					node = repWithLeft(node);
				}
			}
			
		}else {
			if(node.right == null || node.left == null) {
				node = node.right != null ? node.right : node.left; 
			}else {
				
				if(height(node.right) > height(node.left)) {
					T minRight = getMin(node.right);
					node.t = minRight;
					node.right = remove(minRight,node.right);
				}else {
					T maxLeft = getMax(node.left);
					node.t = maxLeft;
					node.left = remove(maxLeft,node.left);
				}
			}
			
		}
		if(node != null) {
			node.height = Math.max(height(node.left), height(node.right)) + 1;
		}
		return node;
		
	}
	
	private AvlNode<T> repWithRight(AvlNode<T> node){
		
		System.out.println("right : " + node.t);
		AvlNode<T> temp = node;
		node = node.right;
		
		temp.right = node.left;
		node.left = temp;
		
		
		temp.height = Math.max(height(temp.left), height(temp.right)) + 1;
		node.height = Math.max(height(node.left), height(node.right)) + 1;
		
		System.out.println("node : " + node.t + ",node height : " + node.height);
		
		return node;
		
	}
	
	private AvlNode<T> repWithLeft(AvlNode<T> node){
		
		System.out.println("left : " + node.t);
		AvlNode<T> temp = node;
		node = node.left;
		
		temp.left = node.right;
		node.right = temp;
		
		temp.height = Math.max(height(temp.left), height(temp.right)) + 1;
		node.height = Math.max(height(node.left), height(node.right)) + 1;
		
		
		System.out.println("node : " + node.t + ",node height : " + node.height);

		return node;
		
	}
	
	private AvlNode<T> repDoubleRight(AvlNode<T> node){
		
		System.out.println("doubleright : " + node.t);
		
		node.right = repWithLeft(node.right);
		return repWithRight(node);
	}
	
	private AvlNode<T> repDoubleLeft(AvlNode<T> node){
		
		System.out.println("doubleleft : " + node.t);
		
		node.left = repWithRight(node.left);
		return repWithLeft(node);
	}
	
	private int height(AvlNode<T> node) {
		
		if(node == null) {
			return -1;
		}
		return node.height;
		
	}
	
	public T getMax() {
		return null;
	}
	
	private T getMax(AvlNode<T> node) {
		while(node.right != null) {
			node = node.right;
		}
		return node.t;
	}
	
	public T getMin() {
		return null;
	}
	
	private T getMin(AvlNode<T> node) {
		while(node.left != null) {
			node = node.left;
		}
		return node.t;
	}
	
	public void showTree() {
		
		showNode(root,"");
	}
	
	private void showNode(AvlNode<T> node,String depstr) {
		
		if(node == null) {
			return;
		}
		
		int dep = depstr.length();
		
		for(int i = 0; i < dep ; i++) {
			if(i != dep - 1) {
				if("1".equals(depstr.substring(i,i+1))){
					System.out.print("│  ");
				}else {
					System.out.print("   ");
				}
			}else {
				if("1".equals(depstr.substring(i,i+1))){
					System.out.print("├─");
				}else {
					System.out.print("└─");
				}
			}
		}
		System.out.println(node.t);	
		String flag = "0";
		if(node.right != null) {
			flag = "1";
		}
		showNode(node.left,depstr + flag);
		showNode(node.right,depstr + "0");
	}
	
}
